package 剑指Offer1;


public class _41重建二叉树 {
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x; }
     }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,0, preorder.length-1,
                     inorder,0,inorder.length-1);
    }

    public TreeNode build(int[] preorder,int preStart,int preEnd,int[] inorder,int inorderStart,int inorderEnd){
        if(preStart>preEnd || inorderStart>inorderEnd) return null;
        int rootVal = preorder[preStart];
        int index = -1;
        for(int i=inorderStart;i<=inorderEnd;i++){
            if(rootVal == inorder[i]){
                index = i;
                break;
            }
        }
        int leftSize = index - inorderStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder,preStart+1,preStart+leftSize,
                          inorder,inorderStart,index-1);
        root.right = build(preorder,preStart+leftSize+1,preEnd,
                           inorder,index+1,inorderEnd);
        return root;
    }
}
